import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Graph<D,V>{
    //D是节点数据的类型  V是权值类型
    ArrayList<D> data ;//图中节点的信息
    //期望以data的长度来表示节点的数目

    int[] id  ,od ;//图的入度和出度

    private boolean [] isVis;//记录某个节点是否被访问过

    private V [][] v;//记录图的连通关系和权值(边集)

    private int arcnum;//边的数目

    public Graph(V [][] v ,ArrayList<D> data,int arcnum){
        this.v = v;
        this.id = new int[data.size()];
        this.od = new int[data.size()];
        this.data = data;
        this.isVis = new boolean[data.size()];
        this.arcnum = arcnum;
    }

    private void visit(int v){
        System.out.print(data.get(v));
    }

    private int FristAdjVex(int v0){
        for(int i = 0; i<data.size(); i++){
            if(v[v0][i] != null) return i;
        }
        return -1;
    }
    private int NextAdjVex(int v0,int w){
        for(int i = w+1; i<data.size(); i++){
            if(v[v0][i] != null) return i;
        }
        return -1;
    }

    private boolean isVis(int v){
        return isVis[v];
    }

    public void InitIsVis(){
        for(int i = 0; i<isVis.length; i++) isVis[i] = false;
    }

    public void FindIOd() {
        for(int i = 0; i < v.length; i++) {
            for(int j = 0; j < v[i].length; j++) {
                if(v[i][j] != null) {
                    id[j] ++;
                    od[i] ++;
                }
            }
        }
    }
    public void DFS(int v0){
        visit(v0);
        isVis[v0] = true;
        int w = FristAdjVex(v0);
        while(w != -1){
            if(!isVis(w))
                DFS(w);
            w = NextAdjVex(v0, w);
        }
    }

    public void BFS(int v0){
        visit(v0);
        isVis[v0] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v0);
        while(!queue.isEmpty()) {
            int v = queue.poll();
            int w = FristAdjVex(v);
            while (w != -1) {
                if(!isVis(w)) {
                    System.out.print(data.get(w));
                    isVis[w] = true;
                    queue.offer(w);
                }
                w = NextAdjVex(v, w);
            }
        }
    }
}